-. Докажіть, що загальна кількість відмінних одна від однопідмножин множини з n елементів дорівнює 2n .
Для доведення скористаємося першим принципом математичної індукції.
при n = 1 множина складається з одного елемента, відповідно маємо дві підмножини – порожню і сам елемент.
Припустимо, що при n = k кількість підмножин 2k.
Доведемо істиність твердження при n = k + 1. При переході від кількості елементів n = k до n = k + 1 крім існуючих при n = k 2k підмножин додається ще 2k підмножин, які утворюються шляхом додавання до вже існуючих підмножин нового елементу. В такому випадку загальна кількість підмножин дорівнює 2k + 2k = 2k + 1 що і треба було довести.
-. Нехай V={a,в,c,d}. Визначить рефлексивне, симетричне, транзитивне відношення на V, що включає (a,в)(в,c) i (c,d).
{(a,a),(b,b),(c,c),(d,d),(a,b),(b,a),(b,c),(c,b),(c,d),(d,c),(a,c),(c,a),(b,d),(d,b),(a,d),(d,a)}
-. Нехай U,V i W такі множини, що U V i V W.
Докажить, що U W.
Для доведення цього твердження необхідно довести що б.я. елемент, що належить множині U, належатиме і множині W. (за визначенням оператора належності). За умовою задачі U V, а це означає, що довільний елемент х, що належить множині U належить і множині V. За другою умовою задачі - V W, отож довільний елемент х, що належить множині V належить і множині W. Отож без втрати узагальнення можна сказати, що довільний елемент х, що належить множині U, належить і множині W. З цього випливає, що U W, що і треба було довести.
-. Нехай А -непуста множина, і нехай R - відношення на А з тою властивістю, що аRв для любих елементів а і в в А (а і в не обов язково різні). Покажить, що R - відношення еквівалентності на А. Визначить класи еквівалентності.
За умовою задачі – довільні два елементи з множини А знаходятися у відношенні R. доведемо, що відношення R володіє властивостями рефлексивності, симетричності і транзитивності.
Рефлексивність. Для довільного елементу а з множини А за умовою задачі справедливо твердження aRa.
Симетричність. Для довільних елементів a, b з множини А справедливо твердження aRb і bRa, за умовою задачі.
Транзитивність. Для довільних елментів a, b, c з множини А справедливо твердження aRb і bRc/
Отож відношення R є відношенням еквівалентності.
Довільний елемент множини А - хі знаходиться у відношенні з довільним елементом xj а отож всі елементи складають один клас еквівалентності, за визначанням класу еквівалентності.
-. Нехай G1 i G2 - ізоморфні графи. Докажить, що якщо G1 - зв’язний граф, то G2 також буде зв’язним.
Для того, щоб довести зв’язність графа G2 необхідно довести існування між довільними двома його вершинами простого ланцюга. Розглянемо довільні дві вершини х’ і у’ графа G2. За визначенням ізоморфізму графів вершинам х’ і у’ графа G2 відповідають вершини х і у графа G1. Оскільки за визначенням граф G1 є зв’язним, то між вершинами х і у існує простий ху ланцюг. Доведемо, що довільному ребру з цього ланцюга відповідає ребро в графі G2 і тим самим доведемо існування простого ланцюга між х і у. Для цього розглянемо довільне ребро (а, b) простого ху ланцюга. Вершинам а і b, що утворюють це ребро відповідають вершини а’ і b’ графа G2, причому за визначенням ізоморфізму графів вершини а’ і b’ графа G2 зв’язані між собою ребром. Таким чином довільні дві вершини х’ і у’ графа G2 зв’язані між собою простим ланцюгом, а отож граф G2 є зв’язним, що і треба було довести.
